package com.clstu.sort;

import java.util.Arrays;

/**
 * 研究堆排序, 基于顺序存储二叉树和堆(大根堆和小根堆统称为堆)
 */
public class HeapSort {
    public static void main(String[] args) {
//        int[] arr = {6,5,4,3,2,1,0};
//        heapSort(arr);
//        System.out.println(Arrays.toString(arr));
        //测试速度
        int arrSize = 8;
        int[] arr = new int[arrSize];
        int[] arr1 = new int[arrSize];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random()*80000);
            arr1[i] = arr[i];
        }
        long start = System.currentTimeMillis();
        heapSort(arr);
        long end = System.currentTimeMillis();
        System.out.println("堆排序"+arr.length+"个数据耗时:"+(end-start)+"ms");//1735ms
        System.out.println("排完序后是否有序:"+isSorted(arr));
        System.out.println("排序后:"+Arrays.toString(arr));
        System.out.println("==========");
        start = System.currentTimeMillis();
        heapSort0(arr1);
        end = System.currentTimeMillis();
        System.out.println("堆排序(insert版)"+arr1.length+"个数据耗时:"+(end-start)+"ms");//1735ms
        System.out.println("排完序后是否有序:"+isSorted(arr1));
        System.out.println("排序后:"+Arrays.toString(arr1));

    }


    //把下标为index的元素调整到堆的合适位置,使其结构仍然是堆结构(该元素的下面都是堆结构)
    public static void adjustHeap(int[] arr, int index ,int heapSize){
        //思路分析:
        //不断的跟自己的孩子比较 如果大于自己的两个孩子,break ,否则,将较大的孩子作为堆顶,堆顶
        int temp = arr[index];//临时变量,最后做交换用
        for (int i = index*2+1; i < heapSize; i=i*2+1) {
             //找到大的孩子的下标
            if(i+1<heapSize && arr[i+1]>arr[i]){
                i++;
            }
            //较大的孩子跟堆顶比较
            if(arr[i]>temp){
                //如果孩子赢了就让孩子当新的堆顶
                //一路向上提,依次前移
                arr[index] = arr[i];
                index = i;
            }else {
                //如果都打过了两个孩子
                break;
            }
        }
        //找到了正确的堆位置放入
        arr[index] = temp;
    }

    //编写方法将某个下标的数插入到前面的堆里(假设index之前都是形成了堆结构)
    public static void heapInsert(int[] arr, int index){
        //思路,一路向上,跟父节点比较,如果大于,跟父节点交换,否则,停
        for (int i = index ; i>=0;i=(i-1)/2){
            if(arr[i]>arr[(i-1)/2]){
                swap(arr,i,(i-1)/2);
            }else {
                break;
            }
        }
    }

    //编写方法堆排序,(helpInsert版,效率略低,实测差不多)
    public static void heapSort0(int[] arr){
        //用heapInsert 的方法形成堆结构
        for (int i = 1; i < arr.length; i++) {
            heapInsert(arr,i);
        }
        //跟最后一个交换,heapSize--....,adjustHeap..
        for (int i = arr.length-1; i > 0 ; i--) {
            //i可以理解为heapSize
            swap(arr,0,i);
            adjustHeap(arr,0,i-1);
        }

    }

    //编写方法实现堆排序
    public static void heapSort(int[] arr){
        //思路分析
        //1.将数组排成堆结构
        //2.不断从堆顶取最大数到最后,然后后再调整剩下的堆,直到取完
        //将数组拍成对结构
        for (int i = arr.length/2-1;i>=0; i--) {
            // (从最后一个不是叶子节点的元素开始向上调整,最后一定能把整个数组形成堆结构!!)
            adjustHeap(arr,i, arr.length);
        }
        //不断取堆顶
        for (int i = arr.length-1; i > 0  ; i--) {
            //交换堆顶跟最后一个数(排好序的部分的前面一个数,也是堆结构的最后一个数)
            swap(arr,0,i);//此时第i个数已经排号序
            adjustHeap(arr,0,i-1);
        }
    }

    //交换数组中的两个数,根据下标
    public static void swap(int[] arr,int index1, int index2){
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    //编写方法判断数组是否已经有序
    public static boolean isSorted(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            if(arr[i]>arr[i+1]) return false;
        }
        return true;
    }
}
